package _11_整理题目._4_动态规划._跳跃游戏;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/jump-game/
 * https://leetcode-cn.com/problems/jump-game/solution/tan-xin-dong-tai-gui-hua-dong-hua-tu-jie-47ie/
 *
 * 一、是否能跳到最后一个位置 n-1，返回 true / false
 *
 * 给定一个非负整数数组nums，假定最开始处于下标为0的位置，
 * 数组里面的每个元素代表下一跳能够跳跃的最大长度。
 * 如果能够跳到数组最后一个位置，则输出true，否则输出false。
 *
 *
 * 动态规划：
 *      标记所有可以跳跃的位置，返回最后一个位置的结果
 *      时间 O(n^2)，空间 O(n)
 *
 * 贪心算法：画进度图覆盖位置 ✅
 *      计算可以跳跃的最远位置，遍历所有可跳跃位置并更新最远位置，与 n-1 比较大小
 *      时间 O(n)，空间 O(1)
 */
public class _01_跳跃游戏_是否可达 {

    // 标记所有可以跳跃的位置
    public boolean canJump1(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        // 取出每个位置的步数 nums[i]，表示可以从位置 i 走 nums[i] 步
        for (int i = 0; i < n; i++) {
            // 如果可以到达位置 i
            if (dp[i]) {
                // 标记从 i 往后的 nums[i] 步，j 代表位置 j
                int step = nums[i];
                for (int j = i; j <= i+step && j < n; j++) {
                    dp[j] = true;
                }
            } else {// 不能到达则直接结束，不需要遍历后面的 nums[i]
                break;
            }
        }
        return dp[n-1];
    }

    // 计算可以跳跃的最远位置，与 n-1 比较
    public boolean canJump2(int[] nums) {
        int n = nums.length;
        int rightMax = 0; // 初始化最开始可以跳跃的最远位置
        for (int i = 0; i <= rightMax; i++) {// 遍历所有可跳跃位置
            rightMax = Math.max(rightMax, i+nums[i]);// 更新最远位置
            // 打印 在位置 i 可到达的最远位置下标，画进度图
//            System.out.println("position i = " + i + ", " + "rightMax = " + rightMax);
            if (rightMax >= n-1) {// 判断是否可达最后一个位置
                return true;
            }
        }
        return false;
    }

    @Test
    public void test() {
        int[] nums = {2,1,3,3,0,0,100};
        System.out.println(canJump1(nums));
        System.out.println(canJump2(nums));
    }
}
